package com.xzz.lru;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author: hhz
 * @create: 2021-12-15 15:39
 * HashMap 在这里主要角色是缓存容器
 * 双向链表则是用来记录缓存数据是否最近使用过 实现 可以在 O(1) 时间复杂度内完成get()和put
 * 对于 get 操作，先判断 key 是否存在 HashMap 中：
 * 1. key 存在，通过 HashMap 获取到对应的 node, 把 node 移动到第一个节点 (head.next)，并返回该节点存储的值。
 * 2. key不存在，则返回null。
 *
 * 对于 put 操作，先判断 key 是否存在 HashMap 中：
 * 1. 如果 key 存在，通过 HashMap 获取到对应的 node，更新该节点的值。并且把node移动到第一个节点 (head.next)。
 * 2. 如果key不存在：
     * 如果 size < capacity， 用 key 和 value 生成一个新的node，插入到双向链表的头部，并将容量加一。
     * 如果 size >= capacity, 把尾部的节点（tail.pre）删除掉。然后用 key 和 value生成一个新的 node，插入到双向链表的头部。
 **/
public class LRUCache {
    //LRU缓存最大容量
    private int capacity;
    Map<Integer,Node<Integer, Integer>> map;
    DoubleLinkedList<Integer, Integer> doubleLinkedList;

    //用LinkedHashMap 可以替代 map和doubleLinkedList 链表头部就是最久未使用的 key
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> prev;//前一个
        Node<K,V> next;//后一个
        Node(){}
        Node(K key,V value){
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }
    class DoubleLinkedList<K, V> {
        Node<K, V> head;//头节点
        Node<K, V> tail;//尾节点
        DoubleLinkedList(){
            head = new Node<>();
            tail = new Node<>();
            head.next = tail;
            tail.prev = head;
        }
        //最近刚使用的加到链表的头部
        public void addHead(Node<K,V> node){
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next=node;
        }
        //删除某个节点
        public void removeNode(Node<K,V> node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            node.prev = null;
        }
        //获取尾部节点
        public Node<K, V> getLast(){
            return tail.prev;
        }
    }
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.doubleLinkedList = new DoubleLinkedList<>();
    }
    public int get(int key) {
        //key不存在，则返回null或者-1
        if(!map.containsKey(key)){
            return -1;
        }else {
            Node<Integer, Integer> node = map.get(key);
            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
            return node.value;
        }
    }
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            map.put(key,node);
            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
        }else {
            if(map.size() >= capacity){
                Node<Integer, Integer> last = doubleLinkedList.getLast();
                map.remove(last.key);
                doubleLinkedList.removeNode(last);
            }
            Node<Integer, Integer> node = new Node<>(key, value);
            map.put(key, node);
            doubleLinkedList.addHead(node);
        }
    }

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        print(lRUCache);
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        print(lRUCache);
        lRUCache.get(1);    // 返回 1
        print(lRUCache);
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        print(lRUCache);
        lRUCache.get(2);    // 返回 -1 (未找到)
        print(lRUCache);
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        print(lRUCache);
        lRUCache.get(1);    // 返回 -1 (未找到)
        print(lRUCache);
        lRUCache.get(3);    // 返回 3
        print(lRUCache);
        lRUCache.get(4);    // 返回 4
        print(lRUCache);
    }
    public static void print(LRUCache lRUCache){
        for (Map.Entry<Integer, Node<Integer, Integer>> en : lRUCache.map.entrySet()) {
            System.out.print(en.getKey()+"="+en.getValue().value);
            System.out.print("  ");
        }
        System.out.println();
    }
}
